import random


# 冒泡排序
def bubble_sort(lists):
    count = len(lists)
    for i in range(0, count):
        for j in range(i, count):
            if lists[i] > lists[j]:
                temp = lists[j]
                lists[j] = lists[i]
                lists[i] = temp
    return lists


'''
插入排序
从前两个开始比较
调整顺序
拓展下一个和前两个比较
不断向前比较满足条件则交换        
'''


# 插入排序
def insert_sort(lists):
    count = len(lists)
    for i in range(1, count):
        key = lists[i]
        j = i - 1
        while j >= 0:
            if lists[j] > key:
                lists[j+1] = lists[j]
                lists[j] = key
            j -= 1
    return lists


def sort1(lists):
    for i in range(1, len(lists)):
        j = i - 1
        key = lists[i]
        while lists[j] > key and j >= 0:
            lists[j+1] = lists[j]
            lists[j] = key
            j -= 1
    return lists



'''
选择排序
不断从数组里找出最小的从前往后替换
第一个与其他的比较找出最小的与之交换
然后从剩下的数组里找出最小与第一个交换        
'''


# 选择排序
def select_sort(lists):
    count = len(lists)
    for i in range(0, count):
        min = i
        for j in range(i + 1, count):
            if lists[min] > lists[j]:
                min = j
        temp = lists[min]
        lists[min] = lists[i]
        lists[i] = temp
    return lists



'''
归并排序-递归版
按大小顺序排列两个等长度数组
设置递归终止条件 长度为1
计算大小num/2划分两个部分
然后不断递归分治
'''

def m(nums):
    if len(nums) <= 1:
        return nums
    mid = len(nums) // 2
    l1 = merge(nums[:mid])
    l2 = merge(nums[mid:])
    return merge(l1, l2)


# 归并排序--递归版
def merge(l1, l2):
    res = []
    i, j = 0, 0
    count1, count2 = len(l1), len(l2)
    while i < count1 and j < count2:
        if l1[i] <= l2[j]:
            res.append(l1[i])
            i += 1
        else:
            res.append(l2[j])
            j += 1
    # 剩下
    res += l1[i:]
    res += l2[j:]
    return res


def merge_sort(lists):
    # 终止递归条件
    if len(lists) <= 1:
        return lists
    num = len(lists) // 2  # python3 整数除法/会变浮点，改为//
    # 递归调用merge分而治之对应位置比较
    l1 = merge_sort(lists[:num])
    l2 = merge_sort(lists[num:])
    return merge(l1, l2)


'''
快速排序
记录起始与结束位置
第一个作为povitkey
从后往前找到小的 找到后放入空位
在从前往后找大的 找到后放入空位
然后分治
'''


def quick_sort_sao(arr):
    if not arr: return
    else:
        pivot = arr[0]
        left = quick_sort_sao([x for x in arr[1:] if x < pivot])
        right = quick_sort_sao([x for x in arr[1:] if x >= pivot])
        return left + [pivot] + right


def quick_sort_opt(array, l, r):
    """
    非递归
    :param array:
    :param l:
    :param r:
    :return:
    """
    if l >= r:
        return
    stack = []
    stack.append(l)
    stack.append(r)
    while stack:
        low = stack.pop(0)
        high = stack.pop(0)
        if high - low <= 0:
            continue
        x = array[high]
        i = low - 1
        for j in range(low, high):
            if array[j] <= x:
                i += 1
                array[i], array[j] = array[j], array[i]
        array[i + 1], array[high] = array[high], array[i + 1]
        stack.extend([low, i, i + 2, high])


# 快速排序
def quick_sort(lists, left, right):
    if left >= right:
        return lists
    key = lists[left]
    low = left
    high = right
    while left < right:
        while left < right and lists[right] >= key:
            right -= 1
        lists[left] = lists[right]
        while left < right and lists[left] <= key:
            left += 1
        lists[right] = lists[left]
    lists[right] = key
    quick_sort(lists, low, left - 1)
    quick_sort(lists, left + 1, high)
    return lists


def get_random_number(num):
    lists = []
    while len(lists) < num:
        lists.append(random.randint(0, 100))
    return lists


# 调整堆
def adjust_heap(lists, i, size):
    lc = 2 * i + 1
    rc = 2 * i + 2
    max = i
    if i < (size/2):
        if lc < size and lists[lc] > lists[max]:
            max = lc
        if rc < size and lists[rc] > lists[max]:
            max = rc
        if max != i:
            lists[max], lists[i] = lists[i], lists[max]
            adjust_heap(lists, max, size)


# 创建堆
def build_heap(lists):
    for i in range(0, int(len(lists)/2))[::-1]:
        adjust_heap(lists, i, len(lists))
    return lists


# 堆排序
def heap_sort(lists):
    lists = build_heap(lists)
    for i in range(0, len(lists))[::-1]:
        lists[0], lists[i] = lists[i], lists[0]
        adjust_heap(lists, 0, i)
    return lists


# 汉诺塔
def move(x, n, z):
    print("将{}上的{}放置在{}上".format(x, n, z))


def hanoi(n, x, y, z):
    if n == 1:
        move(x, 1, z)
    else:
        hanoi(n-1, x, z, y)
        hanoi(1, x, y, z)
        hanoi(n-1, y, x, z)


def guess(x, y):
    return x*x <= y


def sqrt_simple(x):
    i = 1
    res = 0
    while x >= 0:
        x -= i
        i += 2
        res += 1
    return res - 1


def sqrt(x):
    L = 0
    R = x + 1
    ans = 0
    while L < R:
        mid = (L + R)/2
        if (mid**2) <= x:
            ans = mid
            L = mid + 1
        else:
            R = mid
    return ans


if __name__ == '__main__':
    lists = get_random_number(200)
    # print(lists)
    # lists = quick_sort(lists, 0, len(lists)-1)
    # lists = merge_sort(lists)
    # lists = bubble_sort(lists)
    # lists = select_sort(lists)
    # lists = insert_sort(lists)
    # lists = heap_sort(lists)
    print(lists)
    print(sort1(lists))
    # hanoi(5, 'a', 'b', 'c')
    # print(sqrt(16))


